\documentclass[a4paper,10pt]{article}
\usepackage[italian]{babel}
\usepackage[utf8]{inputenc}

\title{Traffic World}
\author{
    Carmine Dodaro, Simone Spaccarotella \\
    \texttt{\{carminedodaro, spa.simone\}@gmail.com}
}

\begin{document}

    \maketitle

    \begin{abstract}
	Traffic World è un framework multi agente per la simulazione del traffico cittadino, mediante agenti
	intelligenti. L'ambiente in cui essi si muovono e con il quale interagiscono, è rappresentato da una mappa
	urbana di una ipotetica città. L'obiettivo di ogni agente è quello di raggiungere la propria destinazione
	nel minor tempo possibile, senza incidenti.
    \end{abstract}

    \section{Introduzione}
	L'ambiente è rappresentato da una mappa cittadina a pianta stradale simmetrica.
	Le strade hanno un senso di marcia predefinito dall'utente (che può generare la propria
	mappa mediante un editor fornito dal programma). Sono previsti sensi unici, doppi sensi
	e rotatorie. Ogni agente deve compiere un determinato percorso, ed è obbligato a mantenere
	il senso di marcia della corsia su cui si trova. Il percorso viene settato dall'utente,
	il quale deve definire il punto di partenza e quello di arrivo dell'agente, cliccando nelle
	celle opportune della mappa (quelle di tipo \emph{Street}).
	
  Ogni agente ha una visione completa del mondo, ma non ha alcuna informazione riguardo
  il numero e la posizione degli altri agenti. Secondo un'accezione alternativa, esso potrebbe considerare
  gli altri agenti come parte integrante dell'ambiente, dunque otterremmo un mondo parzialmente osservabile,
  in quanto non avrebbe accesso allo stato interno degli altri agenti, se non mediante la comunicazione diretta.
  L'ambiente è dunque: parzialmente osservabile, strategico, episodico, semi-dinamico, discreto e multi-agente.
  
	È richiesto che ogni agente raggiunga la propria destinazione minimizzando il tempo
	di percorrenza - direttamente proporzionale alla lunghezza del percorso impiegato,
	maggiorato dai tempi di attesa agli incroci - e le collisioni con altri agenti.
	Quest'ultimo è il requisito con priorità più elevata. Per questa ragione
	viene attribuita una forte penalità agli agenti coinvolti in un incidente. Nel nostro
	sistema ogni agente agisce in modo autonomo, senza l'ausilio di semafori o di
	altri sistemi autonomi di controllo. In questo contesto è importante
	definire una politica di scelte per ogni agente, che consenta di raggiungere un
	obiettivo comune.
	
	\section{Strategie}
    In questa sezione viene descritto l'approccio adottato ai fini della realizzazione
    di tale sistema. E' stato definito un ambiente multiagente, ne quale ogni agente
    può comunicare con gli agenti che si dovessero trovare nei pressi di un incrocio, in modo
    tale da negoziare l'occupazione dello stesso in maniera \emph{fair}, in puro stile
    cooperativo.
    
    \subsection{Ricerca del percorso minimo}
    La mappa stradale è stata modellata con una matrice di oggetti. Ogni cella
    della mappa è una cella della matrice. Gli oggetti possono essere di tipo
    \emph{Street} oppure di tipo \emph{Obstacle}. Quest'ultima classe ha due specializzazioni
    che sono: \emph{Grass} e \emph{House} (di utilità puramente progettuale e grafica).
    
    Per la gestione dei movimenti è stato creato un grafo non orientato, speculare
    alla matrice sopra citata. Ogni cella di tipo \emph{Street} è un nodo del grafo, e
    se due celle sono adiacenti (sempre dello stesso tipo), allora esiste un arco che le collega.
    L'orientamento dell'arco è dato dal senso di marcia che è stato settato sulla corsia che quei
    nodi rappresentano.
    
    Una volta creato il grafo, si passa alla fase di esecuzione. Ogni agente ha un nodo di partenza
    e un nodo di arrivo. Il problema del raggiungimento del punto di arrivo nel minor tempo possibile,
    si riduce al problema di ricerca di un cammino minimo tra due nodi mediante l'algoritmo di Dijkstra.
    L'algoritmo è polinomiale (nella fattispecie è quadratico). 
    Siccome il grafo non è pesato, ovvero ogni arco ha peso omogeneo, la minimizzazione del costo si traduce
    nella minimizzazione delle distanze. Quindi, la ricerca del percorso a costo minimo diventa una ricerca del
    percorso più breve. La risoluzione di questo problema è \emph{offline}. Prima viene calcolato il percorso, e poi
    vengono eseguite le azioni che portino al raggiungimento del nodo target.
    
    \subsection{Minimizzare gli incidenti}
    La strategia di minimizzazione degli incidenti è basata su un concetto di
    collaborazione tra agenti. L'unico punto in cui possono
    avvenire collisioni è l'incrocio e siccome non ci
    sono semafori, ne sistemi di gestione del traffico, è molto importante che
    gli agenti comunichino tra di loro. Ad ogni incrocio dunque, gli agenti che si trovano in
    prossimità negoziano il diritto di attraversamento, mediante una politica basata sulle
    condizioni di traffico e sulla propria velocità.
    
    Sia $t_A$ il traffico dell'agente A e sia $t_B$ il traffico dell'agente B, A
    precede B se $t_A < t_B$. Nel caso in cui $t_A = t_B$, si prende in considerazione la velocità dei
    due agenti. Sia $s_A$ la velocità dell'agente A e sia $s_B$ la velocità
    dell'agente B, A precede B se $s_A > s_B$. Nel caso in cui le due velocità dovessero essere 
    uguali, l'agente che ha iniziato la comunicazione, precederà gli altri.  
    Questo tipo di strategia ha un duplice valore. Infatti, se da una
    parte consente la minimizzazione degli incidenti, allo stesso tempo consente
    di evitare ad agenti con poco traffico nel proprio percorso, di attendere a 
    lungo per agenti con tanto traffico, ottenendo un miglioramento della misura
    di prestazione globale.
    
\end{document}
